/*
https://leetcode-cn.com/problems/insert-delete-getrandom-o1-duplicates-allowed/solution/o1-shi-jian-cha-ru-shan-chu-he-huo-qu-sui-ji-yua-5/
 */
import java.util.*;

public class Solution381 {

    Map<Integer, Set<Integer>> map=new HashMap<>();
    int len=0;
    List<Integer> list=new ArrayList<>();

    public Solution381() {

    }

    public boolean insert(int val) {
        Set<Integer> set=map.getOrDefault(val,new HashSet<>());
        boolean ans= set.size()==0;
        set.add(len);
        list.add(len,val);
        map.put(val,set);
        len++;
        return ans;
    }

    public boolean remove(int val) {
        Set<Integer> set=map.getOrDefault(val,new HashSet<>());
        for (Integer integer : set) {
            Set<Integer> set1=map.get(list.get(len-1));
            if (set!=set1){
                list.set(integer,list.get(len-1));
                set1.remove(len-1);
                set1.add(integer);
                set.remove(integer);
            }else{
                set.remove(len-1);
            }
            len--;
            return true;
        }
        return false;
    }

    public int getRandom() {
        int t=(int)(Math.random()*len);
        return list.get(t);
    }

    public static void main(String[] args) {
        Solution381 solution381=new Solution381();
        System.out.println(solution381.insert(4));
        System.out.println(solution381.insert(3));
        System.out.println(solution381.insert(4));
        System.out.println(solution381.insert(2));
        System.out.println(solution381.insert(4));
        System.out.println(solution381.remove(4));
        System.out.println(solution381.remove(3));
        System.out.println(solution381.remove(4));
        System.out.println(solution381.remove(4));
        System.out.println(solution381.getRandom());
        System.out.println(solution381.getRandom());
    }
}
